package com.lx.algorithm.temp;


import com.leetCode.problem.Problem19;
import com.pojo.ListNode;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-11-13 23:37:40
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-11-13     张李鑫                     1.0         1.0 Version
 */
public class SortInList {
    public static ListNode sortInList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode cur = head;
        head = head.next;
        cur.next=null;

        while (head != null) {
            //记录当前节点
            ListNode temp = head;
            //把当前节点的指针指向下一个地方
            head = head.next;
            //断掉当前节点的next 先比较当前这个节点是否小于 列表头节点如果小于直接挂上去
            if (temp.val < cur.val) {
                temp.next = cur;
                cur = temp;
                continue;
            } else {
                temp.next = null;
            }
            //比较这个节点在cur里面是一个怎么样的状况
            ListNode loop = cur;
            ListNode old = null;
            while (loop != null) {
                old = loop;
                loop = loop.next;
                if ((loop==null)||(temp.val>=old.val&&temp.val<loop.val)){
                    old.next=temp;
                    temp.next=loop;
                    break;
                }
            }
        }
        return cur;
    }


    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode4 = new ListNode(5);
        ListNode listNode1 = new ListNode(3);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(4);

        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;

        ListNode listNode5 = sortInList(listNode);
        System.out.println(123);
    }

}